/**
 * 给定一个模式P，必然含有两个星号，表示可以匹配零个或者任意个字符。
 * 再给定一个字符串S，问S中能匹配P的最短子串的长度。
 * 
 * 将P分为三段，分别计算出哈希，记作P1P2P3
 * 再预处理S的哈希。
 * 然后分别记录三个指针，枚举S的每一个位置作为第一个指针：
 *   当第一个指针开头的子串等于P1
 *   就推动第二个指针往前走，直到。。。
 *   当第二个指针开头的子串等于P2
 *   就推动第三个指针往前走，直到。。。
 *   此时第一个指针到第三个指针的位置就可以匹配P，更新一下答案
 * 总体说来是O(N)
 */

namespace ZIFUCHUAN
{

int const UN = 2;

using hash_t = array<size_t, UN>;
// 10007, 10093
hash_t const Seeds {13313, 10}; // 10用来观察效果
hash_t const ZERO {0, 0};
hash_t const ONE {1, 1};

hash_t const operator + (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] + b[i];
    return ans;
}

hash_t const operator - (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] - b[i];
    return ans;
}

hash_t const operator * (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] * b[i];
    return ans;
}

ostream & operator << (ostream & os, const hash_t & h) {
    os << "[";
    for(int i=0;i<UN;++i){
        os << h[i];
        if(i + 1 == UN) os << "]";
        else os << ",";
    }
    return os;
}

vector<hash_t> Power; // 进制的幂值
void initPower(int n){
    Power.clear();
    Power.reserve(n + 1);
    Power.emplace_back(ONE);

    for(int i=1;i<=n;++i){
        Power.emplace_back(Power.back() * Seeds);
    }

    return;
}

hash_t tr(char c) {
    hash_t ans;
    for(int i=0;i<UN;++i) {
        // ans[i] = c;
        ans[i] = c - 'a' + 1;
    }
    return ans;
}

template<typename IT = string::const_iterator>
struct StrHash
{

/// 
StrHash(IT begin, int n):N(n){
    H.clear();
    H.reserve(N + 1);
    H.emplace_back(ZERO);
    for(int i=1;i<=N;++i){
        H.emplace_back(H.back() * Seeds + tr(*begin++));
    }
    return;
}

/// s[a...b]的哈希, a和b是0-index
hash_t get(int a, int b) const {
    assert(0 <= a and a <= b and b < N);
    // ++a, ++ b;
    // return H[b] - H[a - 1] * Power[b - a + 1];
    return H[b + 1] - H[a] * Power[b - a + 1];
}

vector<hash_t> H;
int N;

};


}

/// 模板偏特化
template<> struct std::hash<ZIFUCHUAN::hash_t> {
    std::size_t operator() (const ZIFUCHUAN::hash_t & p) const {
        std::size_t ret = 0;
        for(auto i : p) ret = ret * 9973 + i;
        return ret;
    }
};

class Solution {
public:
    int shortestMatchingSubstring(string s, string p) {
        if("**" == p) return 0;

        ZIFUCHUAN::initPower(2E5);
        ZIFUCHUAN::StrHash<> Hs(s.begin(), s.length());
        int N = s.length();

        string q[3];
        int cnt = 0;
        for(auto c : p){
            if(c == '*'){
                cnt += 1;
            }else{
                q[cnt] += c;
            }
        }

        vector<int> c;
        vector<ZIFUCHUAN::StrHash<>> Hp;
        for(const auto & qi : q){
            if(qi.empty()) continue;
            Hp.emplace_back(ZIFUCHUAN::StrHash<>{qi.begin(), (int)qi.length()});
            c.emplace_back(qi.length());
        }
        
        vector<vector<int>> v(c.size(), vector<int>{});
        for(int i=0;i<N;++i){
            for(int j=0;j<c.size();++j){
                if(i + c[j] <= N){
                    if(Hs.get(i, i + c[j] - 1) == Hp[j].get(0, c[j] - 1)){
                        v[j].emplace_back(i);
                    }                    
                }

            }
        }

        int ans = -1;
        vector<int> idx(c.size(), 0);
        for(int i=0;i<v[0].size();++i){
            idx[0] = i;
            bool flag = true;
            for(int j=1;j<idx.size();++j){
                while(idx[j] < v[j].size() and v[j][idx[j]] < v[j - 1][idx[j - 1]] + c[j - 1]){
                    idx[j] += 1; 
                }
                if(idx[j] == v[j].size()) {
                    flag = false;
                    break;
                }
            }
            if(flag){
                if(-1 == ans or ans > v.back()[idx.back()] + c.back() - v[0][idx[0]]) {
                    ans = v.back()[idx.back()] + c.back() - v[0][idx[0]];
                }                
            }else{
                break;
            }
        }
        return ans;
    }
};